/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-24
 * Time: 22:10
 */
class Node{
    public int val;
    public Node left;
    public Node right;
    public Node(int val){
        this.val = val;
    }
}
//实现二叉搜索树的基本操作
public class BinarySearchTree {
        public Node root = null;

    /**
     * 查找某一结点的值是否在二叉搜索树中
     * @param key 待查找的值
     * @return 如果在就返回该结点，不在就返回
     */
    public Node sertchKey(int key){
        if(root==null){
            return null;
        }
        Node cur = root;
        //遍历二叉搜索树
        while (cur!=null){   //如果待查找的结点比当前结点的值大，就在该结点的右边查找
            if(cur.val<key){
                cur = cur.right;
            }else if(cur.val>key){ //如果待查找的结点比当前结点值小，就在该结点的左边查找
                cur = cur.left;
            }else { //找到了就返回该结点
                return cur;
            }
        }
        return null; //找不到就返回null
    }

    /**
     * 插入结点
     * @param val 待插入结点的值
     * @return 插入成功返回 true，否则返回 false
     */
    public boolean insert(int val){
        //如果是空树，就创建一个新的结点，直接插入
        if(root==null){
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node parent = null; //用于指向查找的上一个结点
        //遍历二叉搜索树，找到插入结点的上一个结点位置
        while(cur!=null){
            if(cur.val<val){ //如果待插入的结点值比当前结点的值大，就往当前结点的右边走
                parent = cur; //指向当前结点
                cur = cur.right; //遍历当前结点的右边
            }else if(cur.val==val){ //如果待插入结点的值等于当前结点的值，就直接返回
                return false; //不能有相同的数据
            }else{ //待插入的结点值比当前结点的值小，就往当前结点的左边走
                parent = cur;
                cur = cur.left;
            }
        }
        //找到合适的位置后进行插入
        if(val>parent.val){ //如果待插入结点的值比前一个结点值大，就在前一个结点的右边创建一个新的结点进行插入
            parent.right = new Node(val);
        }else { //如果待插入结点的值比前一个结点值小，就在前一个结点的左边创建一个新的结点进行插入
            parent.left = new Node(val);
        }
        return true;
    }

    /**
     * 查找待删除的结点
     * @param key
     */
    public void remove(int key){
        Node cur = root;
        Node parent = null;
        while (cur!=null){
            if(cur.val>key){
                parent = cur;
                cur = cur.left;
            }else  if(cur.val<key){
                parent = cur;
                cur = cur.right;
            }else {
                //当cur指向的结点的值与待删除结点的值相同，就进行删除结点的操作
                removeNode(cur,parent);
                break;
            }
        }
    }

    /**
     * 找到了待删除结点后，进行删除
     * @param cur
     * @param parent
     */
    /**
     * 找到了待删除结点后，进行删除
     * @param cur
     * @param parent
     */
    public void removeNode(Node cur,Node parent){
        if(cur.left==null){  //情况一：cur.left == null
            if(cur==root){
                root = cur.right;
            }else if(cur==parent.left){
                parent.left = cur.right;
            }else { //cur==parent.right
                parent.right = cur.right;
            }
        }else if(cur.right==null){ //情况二：cur.right == null
            if(cur==root){
                root = cur.left;
            }else if(cur==parent.left){
                parent.left = cur.left;
            }else { //cur==parent.right
                parent.right = cur.left;
            }
        }else{ //情况三：cur.left != null && cur.right != null
            Node targetParent = cur;
            Node target = cur.left;
            while (target.right!=null){
                targetParent = target;
                target = target.right;
            }
            target.val = targetParent.val;
            if(target==targetParent.left){
                targetParent.left = target.left;
            }else {
                targetParent.right = target.left;
            }
        }
    }
//    public void removeNode(Node cur,Node parent){
//        if(cur.left==null){  //情况一：cur.left == null
//            if(cur==root){
//                root = cur.right;
//            }else if(cur==parent.left){
//                parent.left = cur.right;
//            }else { //cur==parent.right
//                parent.right = cur.right;
//            }
//        }else if(cur.right==null){ //情况二：cur.right == null
//            if(cur==root){
//                root = cur.left;
//            }else if(cur==parent.left){
//                parent.left = cur.left;
//            }else { //cur==parent.right
//                parent.right = cur.left;
//            }
//        }else{ //情况三：cur.left != null && cur.right != null
//            Node targetParent = cur;
//            Node target = cur.right;
//            while (target.left!=null){
//                targetParent = target;
//                target = target.left;
//            }
//            target.val = targetParent.val;
//            if(target==targetParent.left){
//                targetParent.left = target.right;
//            }else {
//                targetParent.right = target.right;
//            }
//        }
//    }

    public void Inorder(Node root){
        if(root==null){
            return;
        }
        Inorder(root.left);
        System.out.print(root.val+" ");
        Inorder(root.right);
    }

    public static void main(String[] args) {
        int[] array = {9,5,41,2,63,8,74};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0;i<array.length;i++){
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.Inorder(binarySearchTree.root);
        System.out.println("插入重复的数据");
        System.out.println(binarySearchTree.insert(1));
        System.out.println("删除数据：");
        binarySearchTree.remove(1);
        binarySearchTree.Inorder(binarySearchTree.root);
    }
}
